Corelab Seminar
2018-2019
Giorgos Christodoulou
The price of stability of (weighted) congestion games with polynomial latencies
Abstract.
We will discuss results on the price of stability (a notion that compares the social cost of the best Nash equilibrium with the social optimum) of congestion games. We will discuss both the unweighted and weighted version of the problem. In the latter we will discuss exponential lower bounds for the case of polynomial cost functions. Our results close the previous huge gap between Θ(d) and O((d/log d)d) and asymptotically matches the price of anarchy upper bound for polynomial latencies of degree d. On the positive side, we give a general upper bound on the PoS of approximate Nash equilibria, which is sensitive to the range W of the player weights.
Short CV: Giorgos Christodoulou is a Senior Lecturer in the Computer Science Department at the University of Liverpool. He previously held positions as a Visiting Scholar at the Simons Institute for the Theory of Computing, as a Research Group Leader in the Cluster of Excellence on Multimodal Computing and Interaction at the University of Saarland, and as a Postoctoral Researcher at the Max-Planck-Institut for Computer Science in Saarbrucken. His research interests include algorithmic game theory, mechanism design, and online algorithms.